МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Кафедра ЕОМ
Структура даних
"БІНАРНЕ ДЕРЕВО ПОШУКУ"
ЗВІТ
до лабораторної роботи № 7
з
"Програмування. Частина III.
Структури даних та алгоритми"
МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
І. Завдання 1: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
послідовність вершин дерева при проходженні його у прямому порядку;
послідовність листків дерева при проходженні його у зворотньому порядку;
послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне завдання згідно з варіантом.
П, 6.02
Перша літера прізвища студента
День народження студента
Варіант
А, І, С
Б, Ї, Т
В, Й, У
Г, К, Ф
Д, Л, Х
Е, М, Ц
Є, Н, Ч
Ж,О,Ш,Щ
З, П, Ю
И, Р, Я
1, 11, 21
І 1
І 2
І 3
І 4
І 5
І 6
І 7
І 8
І 9
І 10
2, 12, 22
І 10
І 11
І 12
І 13
І 14
І 15
І 16
І 17
І 17
І 19
3, 13, 23
І 9
І 10
І 1
І 2
І 3
І 4
І 5
І 6
І 7
І 8
4, 14, 24
І 10
І 11
І 12
І 13
І 14
І 15
І 16
І 17
І 18
І 19
5, 15, 25
І 7
І 8
І 9
І 10
І 1
І 2
І 3
І 4
І 5
І 6
6, 16, 26
І 6
І 7
І 8
І 9
І 10
І 1
І 2
І 3
І 13
І 5
7, 17, 27
І 15
І 16
І 17
І 18
І 19
І 20
І 11
І 12
І 4
І 14
8, 18, 28
І 4
І 5
І 6
І 7
І 8
І 9
І 10
І 1
І 2
І 3
9, 19, 29
І 13
І 14
І 15
І 16
І 17
І 18
І 19
І 20
І 11
І 12
10, 20, 30
І 2
І 3
І 4
І 5
І 6
І 7
І 8
І 9
І 10
І 1
13. Визначити, чи побудоване дерево є повним деревом.
Код програми
Tree.h
#pragma once
#pragma once
#include <iostream>
using namespace std;
#define T int
class BSTree
{
private:
struct node {
T data;
node *left;
node *right;
};
node* root;
node* CreateLeaf(T);
bool varIsFull = true;
void AddLeafPrivate(T, node*);
void PrintInOrderPrivate(node*);
void PrintPreorderPrivate(node*);
void PrintPostorderPrivate(node*);
node* ReturnNode(T, node*);
T FindSmallestPrivate(node*);
void RemoveNodePrivate(T, node*);
void RemoveRootMatch();
void RemoveMatch(node*, node*, bool);
void isFullPrivate(node*);
void RemoveTree(node*);
public:
BSTree();
~BSTree();
void AddLeaf(T);
void PrintInOrder();
void PrintPreorder();
void PrintPostorder();
T ReturnRootData();
void PrintChildren(T);
T FindSmallest();
void RemoveNode(T);
bool isFull();
};
Tree.cpp
#include "Tree.h"
BSTree::BSTree()
{
root = NULL;
}
BSTree::~BSTree()
{
RemoveTree(root);
}
BSTree::node* BSTree::CreateLeaf(T data)
{
node* n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
void BSTree::AddLeaf(T data)
{
AddLeafPrivate(data, root);
}
void BSTree::AddLeafPrivate(T data, node* Ptr)
{
if (root == NULL)
root = CreateLeaf(data);
else if (Ptr->data > data) {
if (Ptr->left != NULL)
AddLeafPrivate(data, Ptr->left);
else
Ptr->left = CreateLeaf(data);
}
else if (Ptr->data < data) {
if (Ptr->right != NULL)
AddLeafPrivate(data, Ptr->right);
else
Ptr->right = CreateLeaf(data);
}
else
{
cout << "The data " << data << " has already been added to the the tree.\n";
}
}
void BSTree::PrintInOrder()
{
PrintInOrderPrivate(root);
cout << endl;
}
void BSTree::PrintInOrderPrivate(node* Ptr)
{
if (Ptr == NULL) return;
//PrintInOrderPrivate(Ptr->left);
//co...
